package com.wtgroup.demo.mianshi.算法.排序;

/**
 * 从 1 开始, 在有序区中找当前元素应该插入的位置, 大的往后挪, 让出空位.
 * 
 * 思路和抓扑克牌, 排序很像.
 *
 * @author Nisus
 * @version 0.1
 * @date 2019/9/14 23:50
 */
public class InsertSort implements ComparableSort {

    public static void sort(Comparable[] arr) {

       sort(arr, 0, arr.length-1);

    }


    /**给快排用
     * @param arr
     * @param left
     * @param right
     */
    public static void sort(Comparable[] arr, int left, int right) {
        for (int i = left+1; i <= right; i++) {
            Comparable tmp = arr[i];
            int j=i-1;
            while (j >= 0 && arr[j].compareTo(tmp) > 0) {
                // 大的往后挪
                arr[j + 1] = arr[j];
                j--;
            }
            // 遇到小的, 在小的后面放入当前值
            arr[j + 1] = tmp;
        }

    }

}
